package com.fsy.algorithm;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by Administrator on 2017/6/16.
 */
public class Dp {

    private static Integer[] array = new Integer[]{12,80,-12,21,21,3,-7,21,-55,-121,144,222};

    private static Object[][] arrayC = new Object[array.length][2];

    private static  Integer key = 0;

    private static synchronized void keyAdd(){
        key++;
    }
    private static synchronized void keySub(){
        key--;
    }

    public static void main(String[] args){

        while (key<array.length){
            if(array[key] > 0){
                Set<Integer> set = new HashSet<Integer>();

                arrayC[0][0] = set;
                arrayC[0][1] = 0;
                break;
            }
            keyAdd();
        }
        int i = key;
        for(;i<array.length-1;i++){
            compareEle(i);
        }
        for(int j = 0;j<arrayC.length;j++){
            if(null == arrayC[j][0]) break;
            System.out.print(arrayC[j][0] + "======");
            System.out.println(arrayC[j][1]);

        }
        System.out.println("<<<<<<<<<<<<<<<<<<<++++++++++++++++++++>>>>>>>>>>>>>>>>");
        rangeArray();

        for(int j = 0;j<arrayC.length;j++){
            if(null == arrayC[j][0]) break;
            System.out.print(arrayC[j][0] + "======");
            System.out.println(arrayC[j][1]);

        }
    }

    private static void rangeArray() {
        int oldkey = key;
        int i = key-1;
       while (i > 2){
            Integer a =  arrayC[i][1] == null? 0 : (Integer) arrayC[i][1];
            Integer b =  arrayC[i-1][1]  == null? 0 : (Integer) arrayC[i-1][1];
            Integer c =  arrayC[i-2][1]  == null? 0 : (Integer) arrayC[i-2][1];
            if((a+b)>0 && (b+c)>0){
                Set aH = (Set) arrayC[i][0];
                Set bH = (Set) arrayC[i-1][0];
                Set cH = (Set) arrayC[i-2][0];
                cH.add(aH);
                cH.add(bH);
                changeArrayToNULL(i-1);
                changeArrayToNULL(i);
                arrayC[i-2][0] = cH;
                arrayC[i-2][1] = a+b+c;
                arrayMove(i,2);
                break;
            }else{
                i = i-2;
            }
        }

        if(oldkey != key){
            rangeArray();
        }
    }

    private static void changeArrayToNULL(int o) {
        arrayC[o][0] = null;
        arrayC[o][1] = null;
        keySub();
    }

    private static void  compareEle(int index) {
        Integer value = array[index];
        Integer oldV = (Integer) arrayC[key][1];
        if(value == 0){
            Set<Integer> set = (Set<Integer>) arrayC[key][0];
            set.add(index);
            arrayC[key][0] = set;
        }else if(oldV.compareTo(0)==value.compareTo(0)){
            Set<Integer> set = (Set<Integer>) arrayC[key][0];
            set.add(index);
            arrayC[key][0] = set;
            arrayC[key][1] = oldV + value;
        }else{
            Set<Integer> set = new HashSet<Integer>();
            set.add(index);
            keyAdd();
            arrayC[key][0] = set;
            arrayC[key][1] = value;
        }


    }

    private static void arrayMove(int index,int step){

        if(index < step)return;

        for(int i = index ; i < arrayC.length;i++){
            if(null !=arrayC[i][0]) {
                arrayC[i - step][0] = arrayC[i][0];
                arrayC[i - step][1] = arrayC[i][1];
                if(i>= arrayC.length - step){
                    arrayC[i][0] = null;
                    arrayC[i][1] = null;
                }
            }else{
                arrayC[i - step][0] = null;
                arrayC[i - step][1] = null;
            }
        }
    }
}
